#ifndef LIST_HPP
#define LIST_HPP

#include "Allocator.h"
#include "Iterator.h"

class OutOfRange {
};

class LengthError {

};

template <typename T>
struct ListNode {
	T		elem;
	ListNode<T>*	next;
	ListNode<T>*	prev;
};

#ifndef NULL
#define NULL ((void *)0)
#endif


template <class T>
class ListIterator : public Iterator<BidirectionalIteratorTag, T>
{
private:
	ListNode<T> * p;
public:
	ListIterator() : p(0) {}
	ListIterator( ListNode<T> *  x) : p(x) {}
	ListIterator(const ListIterator & b) : p(b.p) {}
	ListIterator & operator=(const ListIterator & b) { p = b.p; return *this;}
	bool operator== (const ListIterator & b) const { return (p == b.p); }	
	bool operator!= (const ListIterator & b) const { return !operator==(b); }
	T& operator* () 
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}

	T operator* () const
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}
	T * operator->()
	{
		if (p)
			return &p->elem;
		throw OutOfRange();
	}

	ListIterator& operator++() 
	{
		if (p)
			p = p->next;
		return *this;
	}


	ListIterator& operator--()
	{	
		if (p)
			p = p->prev;
		return *this;
	}

	ListIterator operator++(int) 
	{
		ListIterator tmp(*this);
		operator++();
		return tmp;
	}
	ListIterator operator--(int)
	{
		ListIterator tmp(*this);
		operator--();
		return tmp;
	}	


	template <typename TT, typename Alloc> friend class List;	
	
};


template <class T>
class ConstListIterator : public Iterator<BidirectionalIteratorTag, T>
{
	const ListNode<T> * p;
public:
	ConstListIterator() : p(0) {}
	ConstListIterator( const ListNode<T> *  x) : p(x) {}
	ConstListIterator(const ConstListIterator & b) : p(b.p) {}
	const ConstListIterator & operator=(const ConstListIterator & b) { p = b.p; return *this;}
	bool operator== (const ConstListIterator & b) const { return (p == b.p); }	
	bool operator!= (const ConstListIterator & b) const { return !operator==(b); }
	const T& operator* () 
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}

	T operator* () const
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}
	T * operator->() const 
	{
		if (p)
			return &p->elem;
		throw OutOfRange();
	}

	ConstListIterator& operator++() 
	{
		if (p)
			p = p->next;
		return *this;
	}


	ConstListIterator& operator--()
	{	
		if (p)
			p = p->prev;
		return *this;
	}

	ConstListIterator operator++(int) 
	{
		ConstListIterator tmp(*this);
		operator++();
		return tmp;
	}
	ConstListIterator operator--(int)
	{
		ConstListIterator tmp(*this);
		operator--();
		return tmp;
	}			
};

template <typename T>
class ListReverseIterator : public Iterator<BidirectionalIteratorTag, T>
{
	T * p;
public:
	ListReverseIterator() : p(0) {}
	ListReverseIterator( ListNode<T> * x) : p(x) {}
	ListReverseIterator(const ListReverseIterator & b) : p(b.p) {}
	ListReverseIterator & operator=(const ListReverseIterator & b) { p = b.p; return *this;}
	bool operator== (const ListReverseIterator & b) { return (p == b.p); }	
	bool operator!= (const ListReverseIterator & b) { return !operator==(b); }
	T& operator* () 
	{
		if (p)
			return p->elem;
		throw OutOfRange();
	}
	T * operator->()
	{
		if (p)
			return &p->elem;
		throw OutOfRange();
	}
	ListReverseIterator& operator++() 
	{
		if (p)
			p = p->prev;
		return *this;
	}
	ListReverseIterator& operator--()
	{	
		if (p)
			p = p->next;
		return *this;
	}
	ListReverseIterator operator++(int) 
	{
		ListReverseIterator tmp(*this);
		operator++();
		return tmp;
	}
	ListReverseIterator operator--(int)
	{
		ListReverseIterator tmp(*this);
		operator--();
		return tmp;
	}	
};

template <typename T, typename Alloc = Allocator<T>  > 
class List {

public:
	typedef typename Alloc::reference reference;
	typedef typename Alloc::const_reference const_reference;
	typedef typename Alloc::size_type size_type;
	typedef typename Alloc::difference_type difference_type;
	typedef	typename Alloc::value_type value_type;
	typedef typename Alloc::pointer pointer;
	typedef typename Alloc::const_pointer const_pointer;

	typedef	Alloc		allocator_type;
	typedef	ListNode<T>	Node;
	typedef	Node *		nodePtr;

	typedef ListIterator<T> iterator;
	typedef ConstListIterator<T>	const_iterator;
	typedef ListReverseIterator<T> reverse_iterator;
	typedef const ListReverseIterator<T> const_reverse_iterator;
	

	explicit List ( const Alloc& = Alloc() ) : head(0),  len(0) { initList();}
	explicit List ( size_type n, const T& value = T(), const Alloc& = Alloc() );
	template < class InputIterator >
	List ( InputIterator first, InputIterator last, const Alloc& = Alloc() );
	List ( const List<T,Alloc>& x );	
	~List () {
		freeList(begin(), end());
		destroyList();
	}

	void swap ( List<T,Alloc>& lst)
	{
		nodePtr tmp = lst.head;
		size_type l = lst.len;

		lst.head = head;
		lst.len = len;
		
		head = tmp;
		len = l;
	}

	template <class InputIterator>
	  void assign ( InputIterator first, InputIterator last );
	void assign ( size_type n, const T& u );
	
	bool empty ( ) const
	{
		return (len == 0);
	}

	size_type size() const	
	{
		return len;
	}
	size_type max_size () const
	{
		return nodeAlloc.max_size();
	}

	void resize ( size_type sz, T c = T() );

	iterator begin ()
	{
		return (head->next);
	}

	const_iterator begin () const	
	{
		return  head->next;
	}

	iterator end ()
	{
		return head;
	}
	const_iterator end () const
	{
		return head;
	}

	reference front ()
	{
		if (empty())
			throw OutOfRange();
		return *begin();
	}
	const_reference front () const
	{
		if (empty())
			throw OutOfRange();
		return *begin();
	}

	reference back ( )
	{
		if (empty())
			throw OutOfRange();	
		return *(--end() );
	}

	const_reference back ( ) const
	{
		if (empty())
			throw OutOfRange();	
		return *(--end() );
	} 

	void push_front ( const T& x )
	{
		insertNode(begin(), x);
	}
	
	void pop_front ()
	{
		if (empty())
			throw OutOfRange();
		freeNode(begin());
	}

	void push_back ( const T& x )
	{
		insertNode(end(), x);
	}
	void pop_back ()
	{
		if (empty())
			throw OutOfRange();
		freeNode(--end());
	}

	iterator insert ( iterator position, const T& x )
	{
		return insertNode(position, x);
	}
	void insert ( iterator position, size_type n, const T& x );
	template <class InputIterator>
	void insert ( iterator position, InputIterator first, InputIterator last );

	iterator erase ( iterator position )
	{
		return freeNode(position);
	}
	iterator erase ( iterator first, iterator last )
	{
		for (; first != last;)
			first = freeNode(first);

		return first;
	}

	void clear()
	{
		freeList(begin(), end());
	}

	void splice ( iterator position, List<T,Alloc>& x );
	void splice ( iterator position, List<T,Alloc>& x, iterator i );
	void splice ( iterator position, List<T,Alloc>& x, iterator first, iterator last );

	void remove ( const T& value );

	template <class Predicate>
	void remove_if ( Predicate pred );

	void reverse ( );

	void sort ( );
	template <class Compare>
	void sort ( Compare comp );
	
	void unique ( );
	template <class BinaryPredicate>
	void unique ( BinaryPredicate binary_pred );

	void merge ( List<T,Alloc>& x );
	template <class Compare>
	void merge ( List<T,Alloc>& x, Compare comp );

	allocator_type get_allocator() const
	{
		return alloc;	
	}

private:
	allocator_type	alloc;
	nodePtr		head;
	size_type 	len;
	Allocator<Node> nodeAlloc;
	
	iterator newNode(const T & x = T())
	{
		nodePtr cur = nodeAlloc.allocate(1);
		alloc.construct(&cur->elem, x);

		return cur;
	}

	void destroyNode(iterator pos)
	{
		alloc.destroy(&(pos.p->elem));
		nodeAlloc.deallocate(pos.p, 1);
	}

	void initList()	
	{
		head = newNode().p;
		head->prev = head->next = head;
	}

	void destroyList()
	{
		destroyNode(head);
	}

	iterator insertNode(iterator pos, const T & x)
	{
		iterator it = newNode(x);
		if (pos == end())	{
			it.p->prev = head->prev;
			head->prev->next = it.p;
			head->prev = it.p;
			it.p->next = head;
		}
		else {
			it.p->prev = pos.p->prev;
			pos.p->prev->next = it.p;
			it.p->next = pos.p;
			pos.p->prev = it.p;
		}
		++len;

		return it;
	}

	iterator insertNode(iterator pos, iterator it )
	{
		if (pos == end())	{
			it.p->prev = head->prev;
			head->prev->next = it.p;
			head->prev = it.p;
			it.p->next = head;
		}
		else {
			it.p->prev = pos.p->prev;
			pos.p->prev->next = it.p;
			it.p->next = pos.p;
			pos.p->prev = it.p;
		}
		++len;

		return it;
	}

	iterator appendNode(iterator pos, const T & x)
	{
		iterator it = newNode(x);

		it.p->prev = pos.p;
		it.p->next = pos.p->next;
		pos.p->next->prev = it.p;
		pos.p->next = it.p;
		
		++len;

		return it;

	}
	
	iterator removeNode(iterator pos)
	{
		if (pos == end())	
			return pos;

		pos.p->prev->next = pos.p->next;
		pos.p->next->prev = pos.p->prev;
		--len;

		return ++pos;
	}	

	iterator freeNode(iterator pos)
	{
		iterator ret = removeNode(pos);
		destroyNode(pos);

		return ret;
	}

	void freeList(iterator first, iterator last)
	{
		for (; first != last; )	
			first = freeNode(first);
	}


};


template <typename T, typename Alloc > 
inline List<T, Alloc>::List ( size_type n, const T& value, const Alloc& ): head(0), len(0) 
{
	initList();
	assign(n, value);
}

template <typename T, typename Alloc > 
template < class InputIterator >
inline List<T, Alloc>::List ( InputIterator first, InputIterator last, const Alloc& ) : head(0), len(0)
{
	initList();
	assign(first, last);
}

template <typename T, typename Alloc > 
inline List<T, Alloc>::List ( const List<T,Alloc>& x ) : head(0), len(0)
{
	initList();
	assign(x.begin(), x.end());
}


template <typename T, typename Alloc > 
template <class InputIterator>
  void List<T, Alloc>::assign ( InputIterator first, InputIterator last )
{
	List<T, Alloc> lst;
	iterator pos = lst.begin();
	for (; first != last; ++first)
			pos = lst.appendNode(pos, *first);
	
	swap(lst);
}

template <typename T, typename Alloc > 
void List<T, Alloc>::assign ( size_type n, const T& u )
{
	List<T, Alloc> lst;
	iterator pos = lst.begin();

	for (size_type i = 0; i < n; ++i)
			pos = lst.appendNode(pos, u);

	swap(lst);
	
}

template <typename T, typename Alloc > 
void List<T, Alloc>::resize ( size_type sz, T c)
{
	size_type diff = 0;
	if (sz == size())
		return;
	if (sz > size()) 
	{
		diff = sz - size();	
		while (diff > 0)
		{
			insertNode(end(), c);
			--diff;
		}
	
	} 
	else
	{
		diff = size() - sz;
		while (diff > 0)
		{
			freeNode(--end());
			--diff;
		}
	}
}

//template <typename T, typename Alloc > 
//List<T, Alloc>::iterator List<T, Alloc>::insert ( iterator position, const T& x )
//{
//	return insertNode(position, x);
//}

template <typename T, typename Alloc > 
void List<T, Alloc>::insert ( iterator position, size_type n, const T& x )
{
	for (size_type i = 0; i < n; ++i)
		insertNode(position, x);
}

template <typename T, typename Alloc > 
template <class InputIterator>
void List<T, Alloc>::insert ( iterator position, InputIterator first, InputIterator last )
{
	for (; first != last; ++first)
		insertNode(position, *first);
}

template <typename T, typename Alloc > 
void List<T, Alloc>::splice ( iterator position, List<T,Alloc>& x )
{
	iterator next;
	for (iterator it = x.begin(); it != x.end(); )
	{	
		next = x.removeNode(it);
		insertNode(position, it);
		it = next;
	}
}

template <typename T, typename Alloc > 
void List<T, Alloc>::splice ( iterator position, List<T,Alloc>& x, iterator i )
{
	x.removeNode(i);
	insertNode(position, i);
}

template <typename T, typename Alloc > 
void List<T, Alloc>::splice ( iterator position, List<T,Alloc>& x, iterator first, iterator last )
{
	iterator next;
	for ( ; first != last; )
	{
		next = x.removeNode(first);
		insertNode(position, first);
		first = next;
	}
}

template <typename T, typename Alloc > 
void List<T, Alloc>::remove ( const T& value )
{
	for (iterator it = begin(); it != end(); )
	{
		if (*it == value)	
			it = freeNode(it);
		else
			++it;
	}
}

template <typename T, typename Alloc > 
template <class Predicate>
void List<T, Alloc>::remove_if ( Predicate pred )
{
	for (iterator it = begin(); it != end(); )
	{
		if (pred(*it))	
			it = freeNode(it);
		else
			++it;
	}
}

template <typename T, typename Alloc > 
void List<T, Alloc>::reverse ( )
{
	List<T, Alloc> lst;
	iterator next;
	for (iterator it = begin(); it != end(); )
	{
		next = removeNode(it);
		lst.insertNode(lst.begin(), it);
		it = next;
		
	}
	swap(lst);
	
}

template <typename T, typename Alloc > 
void List<T, Alloc>::sort ( )
{	
	iterator prev, it, next;

	it = begin();
	++it;
	for (; it != end(); )
	{
		prev = it;
		while ( --prev != (iterator)head )
		{
			if (*prev < *it)	
				break;
		}
		if (++prev != it)
		{
			next = removeNode(it);
			insertNode(prev, it);
			it = next;
		} else {
			++it;
		}
	}
}

template <typename T, typename Alloc > 
template <class Compare>
void List<T, Alloc>::sort ( Compare comp )
{
	iterator prev, it, next;

	it = begin();
	++it;
	for (; it != end(); )
	{
		prev = it;
		while ( --prev != (iterator)head )
		{
			if ( comp(*prev, *it) )	
				break;
		}
		if (++prev != it)
		{
			next = removeNode(it);
			insertNode(prev, it);
			it = next;
		} else {
			++it;
		}
	}

}


template <typename T, typename Alloc > 
void List<T, Alloc>::unique ( )
{
	iterator prev, it;

	prev = it = begin();
	++it;
	for (; it != end(); )
	{
		if (*prev == *it)
		{	
			it = freeNode(it);
		}
		else {
			prev = it;
			++it;	
		}

	}
}

template <typename T, typename Alloc > 
template <class BinaryPredicate>
void List<T, Alloc>::unique ( BinaryPredicate binary_pred )
{
	iterator prev, it;

	prev = it = begin();
	++it;
	for (; it != end(); )
	{
		if (binary_pred(*prev, *it))
		{	
			it = freeNode(it);
		}
		else {
			prev = it;
			++it;	
		}

	}
}


template <typename T, typename Alloc > 
void List<T, Alloc>::merge ( List<T,Alloc>& x )
{
	iterator it1 = x.begin();
	iterator it2 = begin();
	iterator next;
	List<T, Alloc> lst;

	while ((it1 != x.end()) && (it2 != end()) )
	{
		if (*it1 < *it2)			
		{
			next = removeNode(it1);
			lst.insertNode(lst.end(), it1);
			it1 = next;
		}
		else 
		{
			next = removeNode(it2);
			lst.insertNode(lst.end(), it2);
			it2 = next;
		}
	}

	if (it1 != x.end())
	{
		lst.splice(lst.end(), x);
	}

	if (it2 != end() )
	{
		lst.splice(lst.end(), *this);	
	}

	swap(lst);
}

template <typename T, typename Alloc > 
template <class Compare>
void List<T, Alloc>::merge ( List<T,Alloc>& x, Compare comp )
{

	iterator it1 = x.begin();
	iterator it2 = begin();
	iterator next;
	List<T, Alloc> lst;

	while ((it1 != x.end()) && (it2 != end()) )
	{
		if ( comp(*it1,  *it2) )			
		{
			next = removeNode(it1);
			lst.insertNode(lst.end(), it1);
			it1 = next;
		}
		else 
		{
			next = removeNode(it2);
			lst.insertNode(lst.end(), it2);
			it2 = next;
		}
	}

	if (it1 != x.end())
	{
		lst.splice(lst.end(), x);
	}

	if (it2 != end() )
	{
		lst.splice(lst.end(), *this);	
	}

	swap(lst);
}

	
#endif
